package leetcode;

import java.util.HashMap;

/**
 * Created by tiang on 2018/7/5.
 * Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

 get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
 put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

 Follow up:
 Could you do both operations in O(1) time complexity?

 Example:

 LRUCache cache = new LRUCache( 2 );

        cache.put(1, 1);
        cache.put(2, 2);
        cache.get(1);       // returns 1
        cache.put(3, 3);    // evicts key 2
        cache.get(2);       // returns -1 (not found)
        cache.put(4, 4);    // evicts key 1
        cache.get(1);       // returns -1 (not found)
        cache.get(3);       // returns 3
        cache.get(4);       // returns 4
 */

/**
 * 用一个hashMap用来存储<key,value>其中所有的value被封装成一个节点，所有的节点由前后指针组成一个双向队列
 * 队列头表示最新访问或修改的节点
 * 队列为表示最早访问或修改的节点
 * 当get操作时，根据hashmap取出value，并将访问的节点置为头结点
 * 当put操作时，如果原本不存在这个节点，就创建一个新节点并插入队列头，如果此时元素达到上限就删除尾节点
 * 如果原本就存在，则修改原有节点的值，并将其置为头结点
 * 这样可以保证，每次只操作head和tail，时间复杂度为O(1)
 */
public class LRUCache {
    /**
     * 节点类，存储key，value，以及前后指针
     */
    private static class Node{
        public int key;
        public int value;
        public Node pre, next;
        public Node(int k, int v){
            key = k;
            value = v;
            pre = null;
            next = null;
        }
    }

    /**
     * 头指针和尾指针
     */
    private Node head, tail;
    /**
     * 存储键值对
     */
    private HashMap<Integer, Node> cache;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = tail = null;
    }

    /**
     * 获取key对应的value
     * @param key
     * @return
     */
    public int get(int key) {
        if(cache.containsKey(key)) {
            // 将目标节点放在队列头
            Node aim = cache.get(key);
            moveNodeToHead(aim);
            return head.value;
        }
        else
            return -1;
    }

    /**
     * 将目标节点移至头结点
     * @param aim
     */
    private void moveNodeToHead(Node aim){
        // 如果aim不是头结点
        if(head != aim){
            // 如果aim不是头结点，那么aim.pre不可能为空
            // 将前节点的next指向后节点
            aim.pre.next = aim.next;
            if(aim!=tail){
                // 如果aim不是尾节点，那么aim.next不可能为空
                // 将后节点的pre指向前节点
                aim.next.pre = aim.pre;
            }else{
                // 如果aim是尾节点
                // 新的尾节点为aim的前节点
                tail = aim.pre;
            }
            // aim脱离原有位置
            aim.next = head;
            head.pre = aim;
            head = aim;
            aim.pre = null;
        }
    }

    /**
     * 将一个新的节点插入为头结点
     * @param key
     * @param aim
     */
    private void insertIntoHead(int key, Node aim){
        // 如果头结点为空，那么尾节点一定也为空
        if(head == null){
            // 该列表中只存在这一个元素
            // 头结点和尾节点同时指向该元素
            head = tail = aim;
        }else {
            // 新节点的next指向旧的头结点
            aim.next = head;
            // 旧的头结点的pre指向新节点
            head.pre = aim;
            // 将新节点设置为头结点
            head = aim;
        }
        // 将新节点假如map中
        cache.put(key, aim);
    }

    /**
     * 移除旧的尾节点
     */
    private void removeTail(){
        if(tail == null)
            return;
        // 如果尾节点等于头结点，那么该列表只有一个元素，删除之后列表为空
        if(tail == head){
            Node temp = tail;
            tail = head = null;
            // 从列表中删除尾节点
            cache.remove(temp.key);
        }else{
            // 如果尾节点不等于头结点，那么尾节点的pre不为空
            Node temp = tail;
            tail = tail.pre;
            tail.next = null;
            // temp脱离
            cache.remove(temp.key);
        }
    }

    /**
     * 将键值对插入列表
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        if(!cache.containsKey(key)){
            if(cache.size()>=capacity) {
                // 把新节点假如队列头
                Node aim = new Node(key, value);
                removeTail();
                insertIntoHead(key, aim);
            }else{
                Node aim = new Node(key, value);
                insertIntoHead(key, aim);
            }
        }else{
            Node aim = cache.get(key);
            aim.value = value;
            moveNodeToHead(aim);
        }
    }
}
